package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * Description:
 * 给定两个数组，编写一个函数来计算它们的交集。
 * @author: chengrongkai
 * Date: 2021/3/5
 */
public class Solution1 {

    public static void main(String[] args) {
        int[] num1 = {1,2,3,4,5,6};
        int[] num2 = {2,3,6,7,9};
        int[] solution = solutionPlus(num1, num2);
        for (int i : solution) {
            System.out.println(i);
        }
    }

    public static int[] solution(int[] num1,int[] num2){
//        存储交集
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < num1.length; i++) {
            int i1 = num1[i];
            map.put(i1,map.get(i1)==null?1:map.get(i1)+1);
        }
        for (int i = 0; i < num2.length; i++) {
            int i2 = num2[i];
            if (map.get(i2)!=null){
                map.put(i2,map.get(i2)-1);
            }else{
                map.put(i2,1);
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (Integer integer : map.keySet()) {
            if (map.get(integer) == 0){
                result.add(integer);
            }
        }
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }

    /**
     * 假设两个数组已经排好序
     * @param num1
     * @param num2
     * @return
     */
    public static int[] solutionPlus(int[] num1,int[] num2){
        int i=0,j=0;
        ArrayList<Integer> result = new ArrayList<>();
        Arrays.sort(num1);
        Arrays.sort(num2);
        while (i<num1.length&&j<num2.length){
            if (num1[i] > num2[j]){
                j++;
            }else if(num1[i] == num2[j]){
                result.add(num1[i]);
                i++;
                j++;
            }else{
                i++;
            }
        }
        int[] resultArray = new int[result.size()];
        for (int t = 0; t < result.size(); t++) {
            resultArray[t] = result.get(t);
        }
        return resultArray;
    }
}
